import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {
    //股票
    public int maxProfit(int[] prices) {
        int max = prices[0];
        int min = prices[0];
        int len = prices.length;
        int tmp = 0;

        for(int i = 0; i < len  ; i ++) {
            if (prices[i] >= max) {
                max = prices[i];
            }
            if(prices[i] <= min) {
                min = prices[i];
                max = prices[i];
            }
            if(i== len-1||prices[i] > prices[i + 1]) {
                tmp = tmp + max -min;
                min = prices[i];
                max = prices[i];

            }

        }
        return tmp;
    }
    //跳跃游戏
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int tmp = 0;
        Boolean cur = false;
        if(len == 1) {
            return true;
        }
        for(int i = 0; i < len-1 ;i++) {
            if(nums[i] == 0) {
                cur = false;
                int j = i - 1;
                while(j >= 0) {
                    if(nums[j] > i-j) {
                        cur = true;
                    }
                    j--;
                }
                if(!cur) {
                    return false;
                }
            }
        }
        return true;
    }
    //判断子序列
    public boolean isSubsequence(String s, String t) {
        int sl = s.length();
        int tl = t.length();
        int count = 0;
        for(int i = 0; i < tl; i++) {
            if(t.charAt(i) == s.charAt(count)) {
                count++;
            }
            if(count == sl) {
                return true;
            }
        }
        return false;
    }
    //
    public int[] twoSum(int[] numbers, int target) {
        int len = numbers.length;
        int[] arr = new int[2];
        int min = 0;
        int max = 1;
        int tmp = 0;
        for(int i = 1; i < len ; i++) {
            if(numbers[min] +  numbers[i]== target  && numbers[min] != numbers[i] ) {
                max = i;
                tmp = 1;
                break;
            }
            if( i < len-1 && numbers[min] + numbers[i+1] > target) {
                max = i;
                while(numbers[min] +  numbers[i]!= target && numbers[min] != numbers[i]) {
                    min++;
                }
                tmp = 1;
                break;
            }
        }
        if(tmp != 1) {
            max = len - 1;
            while(numbers[min] +  numbers[len-1]!= target && numbers[min] != numbers[len - 1]) {
                min++;
            }
        }
        arr[0] = min + 1;
        arr[1] = max + 1;
        return arr;
    }
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character,Integer> map = new HashMap<>();
        int rl = ransomNote.length();
        int ml = magazine.length();
        for(int i = 0; i < ml;i++) {
            if(map.containsKey(magazine.charAt(i))) {
                map.put(magazine.charAt(i),map.get(magazine.charAt(i)) + 1);
            } else {
                map.put(magazine.charAt(i),1);
            }
        }
        for(int i = 0; i < rl ;i++) {
            if(!map.containsKey(magazine.charAt(i))) {
                return false;
            }
            if(map.containsKey(magazine.charAt(i))&&map.get(magazine.charAt(i)) == 0) {
                return false;
            }
            map.put(magazine.charAt(i),map.get(magazine.charAt(i)) - 1);
        }
        return true;
    }
    public int canConstruct1(String ransomNote, String magazine) {
        // 定义一个哈希映射数组
        int count = 1;
        Boolean tmp = true;
        int[] record = new int[26];
        // 遍历
        for(char c : magazine.toCharArray()){
            record[c - 'a'] += 1;
        }
        for(char c : ransomNote.toCharArray()){
           count = count * record[c - 'a'];
        }
        return count;
    }
    public boolean isIsomorphic(String s, String t) {
        int[] arr1 = new int[200];
        int[] arr2 = new int[200];
        int sl = s.length();
        int tl = t.length();
        for(char c : s.toCharArray()){
            arr1[c ] += 1;
        }
        for(char c : t.toCharArray()){
            arr2[c] += 1;
        }
        for(int i = 0; i < sl&&i < tl ; i++) {
            if(arr1[s.charAt(i)] != arr2[t.charAt(i)]) {
                return false;
            }
        }
        for(int i = 1; i < sl&&i < tl ; i++) {
            if(s.charAt(i) != s.charAt(i-1) && t.charAt(i) == t.charAt(i-1)) {
                return false;
            }
            if(s.charAt(i) == s.charAt(i-1) && t.charAt(i) != t.charAt(i-1)) {
                return false;
            }
        }
        return true;
    }
}
